|
In computing, a hash table (hash map) is a data structure used to implement an associative array, a structure that can map keys to values. A hash table uses a hash function to compute an ''index'' into an array of ''buckets'' or ''slots'', from which the desired value can be found. Ideally, the hash function will assign each key to a unique bucket, but it is possible that two keys will generate an identical hash causing both keys to point to the same bucket. Instead, most hash table designs assume that hash ''collisions''—different keys that are assigned by the hash function to the same bucket—will occur and must be accommodated in some way. In a well-dimensioned hash table, the average cost (number of instructions) for each lookup is independent of the number of elements stored in the table. Many hash table designs also allow arbitrary insertions and deletions of key-value pairs, at (amortized〔Charles E. Leiserson, (''Amortized Algorithms, Table Doubling, Potential Method'' ) Lecture 13, course MIT 6.046J/18.410J Introduction to Algorithms—Fall 2005 〕) constant average cost per operation.〔 〕〔 In many situations, hash tables turn out to be more efficient than search trees or any other table lookup structure. For this reason, they are widely used in many kinds of computer software, particularly for associative arrays, database indexing, caches, and sets. ==Hashing== (詳細はmodulo operator ( %).In the case that the array size is a power of two, the remainder operation is reduced to masking, which improves speed, but can increase problems with a poor hash function. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「hash table」の詳細全文を読む スポンサード リンク
|